前言

在上一篇文章中，我們認識了數論與模運算，理解了加法、乘法如何在模數的限制下運作，也學會使用 Java 的 BigInteger.modPow() 進行模指數運算。

這些知識已經讓我們看懂 RSA 公式的一部分：

c ≡ m^e mod n

但接下來會遇到幾個問題：

• RSA 如何挑選公開金鑰中的指數 e？
• 私密金鑰中的指數 d 是怎麼算出來的？
• 為什麼 e 和 d 需要滿足特定的數學關係？
• 為什麼經過加密與解密之後，原始訊息能夠恢復？

要回答這些問題，我們需要進一步認識幾個數論工具。

今天的目標，是把這些工具一步一步串起來，理解 RSA 金鑰生成背後的數學邏輯。

一、最大公因數：兩個數有多「互相獨立」？

首先介紹最大公因數，英文是 Greatest Common Divisor，簡稱 GCD。
例如，12 和 18 的公因數有：

• 1
• 2
• 3
• 6

其中最大的就是 6，因此：

gcd(12,18)=6

再看另一個例子：

gcd(8,15)=1

這代表 8 和 15 沒有大於 1 的共同因數。數學上，我們稱這兩個數互質（Coprime）。
注意，互質不代表兩個數都是質數。例如 8 不是質數，15 也不是質數，但它們仍然互質。

為什麼 RSA 在意互質？

在 RSA 金鑰生成過程中，我們會選擇一個公開指數 e，並要求：

gcd(e,φ(n))=1

這裡的 φ(n) 是歐拉函數，稍後會介紹。

為什麼需要這個條件？因為只有當 e 與 φ(n) 互質時，e 才存在模 φ(n) 的乘法反元素。這個反元素，就是 RSA 私密指數 d 的數學基礎。

因此，計算最大公因數不是單純的數學練習，而是 RSA 金鑰生成的重要步驟。

二、歐幾里得演算法：快速求出最大公因數

如果直接列出兩個數的所有因數，再找出最大公因數，當數字變得很大時，效率就會很差。
歐幾里得演算法（Euclidean Algorithm）提供了一個更有效率的方法。
它的核心概念是：

gcd(a,b)=gcd(b,a mod b)

也就是說，兩個數的最大公因數，可以轉換成「較小的數」與「兩數相除後的餘數」的最大公因數。
只要不斷重複這個步驟，直到餘數變成 0，最後一個非零餘數就是最大公因數。

範例：計算 gcd(252, 105)

依序進行除法：
252=2105+42
所以：
gcd(252,105)=gcd(105,42)
繼續計算：
105=242+21
因此：
gcd(105,42)=gcd(42,21)
最後：
42=2*21+0
餘數已經是 0，所以答案是：
gcd(252,105)=21}
整個過程可以整理如下：

Java 實作

Java 的 BigInteger 已經提供 gcd() 方法：

import java.math.BigInteger;

public class GcdExample {
    public static void main(String[] args) {
        BigInteger a = new BigInteger("252");
        BigInteger b = new BigInteger("105");

        System.out.println(a.gcd(b)); // 21
    }
}

在實際密碼學程式中，數字可能有數百甚至數千個位元，因此應使用 BigInteger，而不是一般的 int 或 long。

三、擴展歐幾里得演算法：不只知道答案，還要找到係數

一般的歐幾里得演算法只能告訴我們最大公因數是多少。
擴展歐幾里得演算法（Extended Euclidean Algorithm）則更進一步：它可以找到整數 x 和 y，使得：
** ax + by = gcd(a,b)**
這個等式稱為 Bézout 等式。

為什麼我們需要知道 x 和 y？
因為當：
gcd(a,n) = 1
就能找到整數 x 和 y，滿足：
ax + ny = 1
把等式兩邊對 n 取模：
ax + ny ≡ 1 mod n
由於 ny 一定是 n 的倍數，所以：
ax ≡ 1 (mod n)
這正是模反元素的定義。

換句話說，擴展歐幾里得演算法可以幫我們找到模反元素。

範例：求出 17 在模 3120 下的反元素

我們想找一個整數 d，使得：
17d ≡ 1 (mod 3120)
先使用歐幾里得演算法：
3120=18317+9
=>17=19+8
=>9=18+1
=>8=81+0
因此：
gcd(17,3120)=1
接著反向整理餘數。

由第三個等式：1=9-8
由第二個等式：8=17-9
代回去：1=9-(17-9)=29-17
再由第一個等式：
9=3120-18317
代入：
1=2(3120-18317)-17
整理後：
1=23120-36717
所以：
(-367) * 17 ≡ (1 mod 3120)
模反元素可以用非負的代表值表示，因此：
-367 mod 3120 = 2753
最後得到：
17^{-1}≡2753 (mod 3120)
驗算：
172753=46801
而：
46801=153120+1
所以：
172753 ≡ 1 (mod 3120)
答案正確。

Java 實作：直接求模反元素

Java 的 BigInteger 提供 modInverse()，可以直接計算模反元素：

import java.math.BigInteger;

public class ModularInverseExample {
    public static void main(String[] args) {
        BigInteger e = BigInteger.valueOf(17);
        BigInteger phi = BigInteger.valueOf(3120);

        BigInteger d = e.modInverse(phi);

        System.out.println(d); // 2753

        // 驗證 e * d mod phi 是否等於 1
        System.out.println(e.multiply(d).mod(phi)); // 1
    }
}

如果兩個數不互質，模反元素就不存在，modInverse() 會拋出 ArithmeticException。

四、歐拉函數：計算與 n 互質的正整數有多少個

歐拉函數（Euler's Totient Function）記作：φ(n)
它代表從 1 到 n 之間，有多少個正整數與 n 互質。

範例：計算 φ(10)

從 1 到 10 的整數中：

符合條件的數字是 1、3、7、9，一共有 4 個。
因此：φ(10)=4

RSA 為什麼可以快速計算歐拉函數？

RSA 會選擇兩個不同的質數 p 和 q，並計算：n=pq
當 p 和 q 是不同質數時，可以使用：
φ(n)=(p-1)(q-1)}
原因是：1 到 pq 之間，不能與 pq 互質的數，正好是 p 或 q 的倍數。排除這些數之後，剩下的互質數量就是 (p-1)(q-1)。
以 RSA 教學範例為例，假設：
p=61,q=53
則：n= 6153 = 3233
而：φ(n) = (61-1)(53-1) = 6052
=> φ(n)=3120
這個 3120，就是前面計算模反元素時使用的數字。

五、歐拉定理：為什麼模指數運算可以還原？

接下來是理解 RSA 的關鍵數學定理。
歐拉定理（Euler's Theorem）指出，當 a 與 n 互質時：
a^φ(n) ≡ 1 (mod n)
它的使用條件很重要：gcd(a,n)=1，不能忽略這個前提。

範例：驗證歐拉定理

令：a=3,n=10
因為：gcd(3,10)=1
而：φ(10)=4
根據歐拉定理：
3^4 ≡ 1 (mod 10)
實際計算：
3^4 = 81
而：81 mod 10 = 1 ，結果符合定理。

費馬小定理：質數情況下的特例

如果模數 p 是質數，而且 p 不整除 a，則：
a^{p-1} ≡ 1 (mod p)
這就是費馬小定理（Fermat's Little Theorem）。

例如，因為 7 是質數，且 3 不能被 7 整除：
3^{7-1} ≡ 1 (mod 7)
也就是：3^6=729
729 mod7=1
費馬小定理可以視為歐拉定理在質數模數下的特例，因為當 p 是質數時：
φ(p) = p-1

六、把數學串起來：RSA 的 d 到底怎麼來？

現在，我們已經認識 RSA 金鑰生成所需的主要數學工具。
假設 RSA 選擇兩個不同的質數：
p=61,q=53

步驟 1：計算模數 n

n = pq = 61*53 = 3233
公開金鑰與私密金鑰都會使用這個 n。

步驟 2：計算歐拉函數

φ(n) = (p-1)(q-1) = 3120

步驟 3：選擇公開指數 e

選擇：e=17
並確認：gcd(17,3120)=1
因為兩者互質，所以模反元素存在。

步驟 4：求出私密指數 d

我們要找到 d，使得：
ed ≡ 1 (mod φ(n))
也就是：
17d ≡ 1 (mod 3120)
透過擴展歐幾里得演算法，得到：
d=2753
此時，金鑰的核心參數就完成了：

• 公開金鑰：(n,e)=(3233,17)
• 私密金鑰的核心參數：(n,d)=(3233,2753)

這裡的數字只是用來示範原理，實務上的 RSA 必須使用足夠大的金鑰，並由可靠的密碼學函式庫產生。

七、為什麼 RSA 加密後還能解密？

RSA 的簡化公式是：
加密：c≡ m^e mod n
解密：m'≡ c^d mod n

把加密公式代入解密公式：
m'≡(m^e)^d mod n

因此：
m'≡ m^{ed}mod n
而我們在金鑰生成時，刻意讓：
ed ≡ 1 (mod φ(n))
所以存在整數 k，使得：
ed = 1 + kφ(n)
於是：
m'≡ m^{1+kφ(n)} (mod n)
在 m 與 n 互質的情況下，根據歐拉定理：
m^{φ(n)} ≡ 1 (mod n)
因此：
m'≡ m (m^{φ(n)})^k (mod n)
m'≡ m*1^k (mod n)
最後得到：
m'≡ m (mod n)

這就是 RSA 加密與解密能夠還原原始數值的數學直覺。

八、Java 的 BigInteger 如何處理 RSA 的大數運算？

前面使用 modInverse() 求模反元素。至於模指數運算，Java 提供 modPow()。

import java.math.BigInteger;

public class RsaMathExample {
    public static void main(String[] args) {
        BigInteger n = BigInteger.valueOf(3233);
        BigInteger e = BigInteger.valueOf(17);
        BigInteger d = BigInteger.valueOf(2753);

        // 假設原始訊息的數值為 65
        BigInteger m = BigInteger.valueOf(65);

        // 加密：c = m^e mod n
        BigInteger c = m.modPow(e, n);
        System.out.println("Ciphertext: " + c); // 2790

        // 解密：m' = c^d mod n
        BigInteger recovered = c.modPow(d, n);
        System.out.println("Recovered: " + recovered); // 65
    }
}

這個範例把數學公式轉成 Java 程式：

• modPow(e, n)：計算模指數運算。
• modInverse(φ)：計算模反元素。
• gcd()：計算最大公因數。

九、工程師需要記住的幾個重點

今天的內容可以濃縮成以下關係：

有一點特別值得記住：這些公式並不是彼此獨立的數學知識，而是一條完整的推導鏈。
GCD ->模反元素 ->選出d ->歐拉定理 ->RSA 還原
理解這條鏈，就能知道 RSA 的金鑰參數為什麼要這樣選，而不是只記住幾個看似神祕的公式。